package LeetCode.interview;

import LeetCode.interview._021_Merge_Two_Sorted_Lists.ListNode;
import util.LogUtils;

/*
 * 
原题

　　Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). 
　　For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

　　But the following is not:

    1
   / \
  2   2
   \   \
   3    3

　　Note: 
　　Bonus points if you could solve it both recursively and iteratively. 
题目大意

　　给定一棵树，判断它是否是对称的。即树的左子树是否是其右子树的镜像。 

解题思路

　　使用递归进行求解，
	先判断左右子结点是否相等，
			不等就返回false，
			相等就将左子结点的右子树与右子结果的左子结点进行比较操作，
				同时将左子结点的右子树与右子结点的左子树进行比较，
			只有两个同时为真是才返回true，否则返回false。
 * @Date 2017-09-13 16：19
 */
public class _101_Symmetric_Tree {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}
	
    public boolean isSymmetric(TreeNode root) {
    	if (root == null)	return true;
    	else return isSame(root.left, root.right);
    }
   
    
    public boolean isSame(TreeNode t1, TreeNode t2) {
    	if (t1==null && t2== null)	return true;
    	if (t1==null&&t2!=null || t1!=null&&t2==null)	return false;
    	return (t1.val==t2.val) && isSame(t1.left, t2.right) && isSame(t1.right, t2.left);
    }
    
	private TreeNode newTree1() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(3, null, 
									new TreeNode(4)), null 
					), 
					new TreeNode(2, 
							null, 	new TreeNode(3, new TreeNode(4), null)
					)
				);
	}
	
	public static void main(String[] args) {
		_101_Symmetric_Tree obj = new _101_Symmetric_Tree();
		LogUtils.println("结果", 
				obj.isSymmetric(
						obj.newTree1()
				));
	}
}
